use std::u32;

const PARTS: [u32; 8] = [1, 2, 5, 10, 20, 30, 50, 100];

pub fn dp_rec_mc(amount: u32) -> u32 {
    let mut dp = vec![u32::MAX; (amount + 1) as usize];
    dp[0] = 0;
    for i in 1..=amount as usize {
        for &part in PARTS.iter() {
            if i >= part as usize {
                dp[i] = dp[i].min(dp[i - part as usize] + 1);
            }
        }
    }
    dp.last().copied().unwrap()
}
